package com.chj.chuji.tijie07;

//https://acm.taifua.com/archives/nowcoderday1l.html
//https://www.pianshen.com/article/499727176/
//https://www.dazhuanlan.com/2019/12/11/5df0ef4f553a4/
//https://blog.csdn.net/Zeolim/article/details/82963250
//https://blog.csdn.net/qq_41835683/article/details/84109433

//https://blog.nowcoder.net/n/246ecaa55cc14352ad4206e715a1b0d1

//https://blog.nowcoder.net/n/246ecaa55cc14352ad4206e715a1b0d1

public class NewGame {
//	#include<bits/stdc++.h>
//	using namespace std;const
//	int maxn = 1005;const
//	double inf = 1e-4;#
//	define INF 0x7f7f7f7f double Graph[maxn][maxn];bool used[maxn];double dis[maxn];
//	int n;
//	int A, B, C1, C2;
//	struct Cir
//	{
//		int x, y, r;
//	}C[maxn];

	public static class Cir {
		public int x, y, r;

		public Cir(int x, int y, int r) {
			this.x = x;
			this.y = y;
			this.r = r;
		}
	}

//	double getCC(int a, int b) // 计算圆心到圆心
//	{
//		return sqrt(abs((C[a].x - C[b].x) * (C[a].x - C[b].x)) + abs((C[a].y - C[b].y) * (C[a].y - C[b].y)));
//	}

//	double getCL(int A, int B, int CC, int v) // 计算圆心到直线
//	{
//		double t = (abs(C[v].x * A + C[v].y * B + CC) / sqrt(A * A + B * B));
//		return t;
//	}

//	void Dijkstra() {
//		int i, x, y, m;
//		memset(used, 0, sizeof(used));
//		for (int i = 0; i <= n + 1; i++) {
//			dis[i] = Graph[0][i];
//		}
//		dis[0] = 0;
//		for (i = 0; i <= n + 1; i++) {
//			m = maxn;
//			x = -1;
//			for (y = 0; y <= n + 1; y++)
//				if (!used[y] && (dis[y] < m || x == -1)) {
//					m = dis[y];
//					x = y;
//				}
//			used[x] = 1;
//			if (x == -1)
//				break;
//			for (y = 0; y <= n + 1; y++)
//				dis[y] = min(dis[y], dis[x] + Graph[x][y]);
//		}
//
//	}

//	int main()
//	{
//	    cin >> n >>A >> B >> C1 >> C2;
//
//	    memset(Graph,0,sizeof(Graph));
//	    ///第一条直线代表起点即0，第2条直线代表终点，即n+1
//	    Graph[0][n+1] = Graph[n+1][0] = abs(C1-C2)/(sqrt(A*A+B*B));///两直线的距离
//
//	    for(int i=1 ; i<=n; ++i)scanf("%d %d %d",&C[i].x,&C[i].y,&C[i].r);
//	    ///建图
//	    for(int i =1; i <= n; i ++)
//	    {
//	        double t = getCL(A,B,C1,i);
//	        ///求第一个直线
//	        if(t - C[i].r <= inf)
//	            Graph[0][i] = Graph[i][0] = 0.0;
//	        else
//	            Graph[0][i] = Graph[i][0] = t - C[i].r;
//	        ///求第二个直线
//	        t = getCL(A,B,C2,i);
//	        if(t - C[i].r <= inf)
//	            Graph[i][n +1] = Graph[n + 1][i] = 0.0;
//	        else
//	            Graph[i][n +1] = Graph[n + 1][i] = t - C[i].r;
//
//	        for(int j = i + 1; j <= n; j ++)
//	        {
//	            ///圆与圆的距离
//	            double t = getCC(i,j);
//	            if( t - (C[i].r+C[j].r) <= inf)Graph[i][j] = Graph[j][i] = 0;
//	            else Graph[i][j] = Graph[j][i] = t-(C[i].r+C[j].r);
//	        }
//	    }
//	    Dijkstra();
//	    printf("%.6f\n",dis[n + 1]);
//	    return 0;
//	}

	public static int n = 2;
	public static int A = 0;
	public static int B = 1;
	public static int C1 = 0;
	public static int C2 = -4;
	public static final int maxn = 5;
	public static double[][] Graph = new double[maxn][maxn];
	public static Cir[] Clist = new Cir[maxn];
	public static final double inf = 1e-4;
	public static boolean[] used = new boolean[maxn];
	public static double[] dis = new double[maxn];

	public static void main(String[] args) {
		System.out.println(String.format("%.10f", inf));
//		int n = 2;
//		int A = 0;
//		int B = 1;
//		int C1 = 0;
//		int C2 = -4;

		/// 第一条直线代表起点即0，第2条直线代表终点，即n+1
		/// 两直线的距离
//		d=|C1-C2|/√bai(A^2+B^2)
//		设两条直线方程为
//		Ax+By+C1=0
//		Ax+By+C2=0
		Graph[0][n + 1] = Math.abs(C1 - C2) / (Math.sqrt(A * A + B * B));
		Graph[n + 1][0] = Math.abs(C1 - C2) / (Math.sqrt(A * A + B * B));
		Cir cir01 = new Cir(0, 1, 1);
		Cir cir02 = new Cir(1, 3, 1);
		Clist[1] = cir01;
		Clist[2] = cir02;

		/// 建图
		for (int i = 1; i <= n; i++) {
			double t = getCL(A, B, C1, i);
			/// 求第一个直线
			if (t - Clist[i].r <= inf) {
				Graph[0][i] = 0.0;
				Graph[i][0] = 0.0;
			} else {
				Graph[0][i] = t - Clist[i].r;
				Graph[i][0] = t - Clist[i].r;
			}
			/// 求第二个直线
			t = getCL(A, B, C2, i);
			if (t - Clist[i].r <= inf) {
				Graph[i][n + 1] = 0.0;
				Graph[n + 1][i] = 0.0;
			} else {
				Graph[i][n + 1] = t - Clist[i].r;
				Graph[n + 1][i] = t - Clist[i].r;
			}

//	        for(int j = i + 1; j <= n; j ++)
//	        {
//	            ///圆与圆的距离
//	            double t = getCC(i,j);
//	            if( t - (C[i].r+C[j].r) <= inf)
//			    Graph[i][j] = Graph[j][i] = 0;
//	            else Graph[i][j] = Graph[j][i] = t-(C[i].r+C[j].r);
//	        }

			for (int j = i + 1; j <= n; j++) {
				/// 圆与圆的距离
				double tc = getCC(i, j);
				if (tc - (Clist[i].r + Clist[j].r) <= inf) {
					Graph[i][j] = 0.0;
					Graph[j][i] = 0.0;
				} else {
					Graph[i][j] = tc - (Clist[i].r + Clist[j].r);
					Graph[j][i] = tc - (Clist[i].r + Clist[j].r);
				}
			}
		}

		System.out.println(Graph);
		Dijkstra();
//	    printf("%.6f\n",dis[n + 1]);
		System.out.println(String.format("%.6f", dis[n + 1]));
	}

//	对于P（x0，y0),它到直线Ax+By+C=0的距离 用公式d=|Ax0+By0+C|/√(A^2+B^2)圆心到弦的距离叫做弦心距
	public static double getCL(int A, int B, int CC, int v) // 计算圆心到直线
	{
		double t = Math.abs((Clist[v].x * A + Clist[v].y * B + CC) / Math.sqrt(A * A + B * B));
		return t;
	}

//	就是先出圆心，利用两点距离公式求。
//	d=√[(x2-x1)²+(y2-y1)²]
	public static double getCC(int a, int b) // 计算圆心到圆心
	{
		return Math.sqrt(Math.abs(((Clist[a].x - Clist[b].x) * (Clist[a].x - Clist[b].x)))
				+ Math.abs((Clist[a].y - Clist[b].y) * (Clist[a].y - Clist[b].y)));
	}

	public static void Dijkstra() {
		int i, x, y, m;
		for (i = 0; i <= n + 1; i++) {
			dis[i] = Graph[0][i];
		}
		dis[0] = 0.0;
		for (i = 0; i <= n + 1; i++) {
			m = maxn;
			x = -1;
			for (y = 0; y <= n + 1; y++)
				if (!used[y] && (dis[y] < m || x == -1)) {
					m = (int) dis[y];
					x = y;
				}
			used[x] = true;
			if (x == -1)
				break;
			for (y = 0; y <= n + 1; y++)
//				if (dis[y] != null && dis[x] != null && Graph[x][y] != null) {
//					dis[y] = Math.min(dis[y], dis[x] + Graph[x][y]);
//				}
				dis[y] = Math.min(dis[y], dis[x] + Graph[x][y]);
		}

	}
}
